#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef char STDataType;

typedef struct stack {
    STDataType* a;
    int capacity;
    int size;
} Stack;

void StackInit(Stack* ps) {
    ps->a = NULL;
    ps->capacity = ps->size = 0;
}

void StackPush(Stack* ps, STDataType data) {
    assert(ps);
    if (ps->size == ps->capacity) {
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        STDataType* tmp =
            (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
        if (tmp) {
            ps->a = tmp;
        }
        else {
            perror("realloc fail");
        }
    }
    ps->a[ps->size] = data;
    ps->size++;
}

void StackPop(Stack* ps) {
    assert(ps);
    assert(ps->size > 0);
    ps->size--;
}

int StackSize(Stack* ps) {
    assert(ps);
    return ps->size;
}
STDataType StackTop(Stack* ps) {
    assert(ps);

    int size = ps->size - 1;
    return ps->a[size];
}

bool StackEmpty(Stack* ps) {
    assert(ps);
    if (StackSize(ps) == 0) {
        return true;
    }
    else {
        return false;
    }
}

void StackDestroy(Stack* ps) {
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->size = ps->capacity = 0;
}

bool isValid(char* s) {
    Stack st;
    StackInit(&st);

    int i = 0;
    while (s[i]) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            StackPush(&st, s[i]);
        }
        else {
            if (StackEmpty(&st))
                return false;
            char left = StackTop(&st);
            StackPop(&st);
            /*if (left == '(') {
                 if (s[i] != ')')
                     return false;
             } else if (left == '[') {
                 if (s[i] != ']')
                     return false;
             } else {
                 if (s[i] != '}')
                     return false;
             }*/
            if ((left == '(' && s[i] != ')') || (left == '{' && s[i] != '}') ||
                (left == '[' && s[i] != ']')) {
                return false;
            }
        }
        ++i;
    }
    bool ret = true;
    if (!StackEmpty(&st)) {
        ret = false;
    }
    StackDestroy(&st);
    return ret;
}

int main() {
    char s[] = { "({{{{}}}))" };
    bool ret=isValid(s);
    if (ret) { printf("true"); }
    else
    {
        printf("false");
    }
    return 0;
}